package com.algorithm.ch1.cjm.linkedlist;

import com.algorithm.ch1.cjm.linkedlist.model.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 寻找第一个相等的节点
 *
 * @Author: Jie Ming Chen
 * @Date: 2019-02-28
 * @Version 1.0
 */
public class FirstCommon {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node1;

        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        node5.next = node6;
        node6.next = node3;

//        ListNode map = map(node1, node5);
//        System.out.println(map.val);

        //ListNode node = firstCommon(node3, node5);
        ListNode nodeX = getFirstCommon(node1, node5);
        System.out.println(nodeX.val);
    }

    /**
     * 第一个相等
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getFirstCommon(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode a = headA, b = headB;
        while (a != b) {
            a = (a != null) ? a.next : headB;
            b = (b != null) ? b.next : headA;
        }
        return a;
    }

    // 第一个相同的节点
    private static ListNode firstCommon(ListNode node1, ListNode node2) {
        boolean ring = isRing(node1);
        if (ring) {
            return fastAndSlow(node1, node2);
        }
        int length1 = getNodeLength(node1);
        int lenght2 = getNodeLength(node2);
        int diff = length1 - lenght2;
        ListNode longNode = node1;
        ListNode shortNode = node2;
        if (diff < 0) {
            longNode = node2;
            shortNode = node1;
            diff = -diff;
        }
        while (diff-- > 0) {
            longNode = longNode.next;
        }
        ListNode firstNode1 = longNode;
        ListNode firstNode2 = shortNode;
        while (!(shortNode != null && shortNode.equals(longNode))) {
            shortNode = shortNode.next;
            longNode = longNode.next;
            if (firstNode1.equals(longNode)) {
                break;
            }
            if (firstNode2.equals(shortNode)) {
                break;
            }
        }
        System.out.println(longNode);
        return longNode;
    }

    /**
     * 是否为环
     *
     * @param node
     * @return
     */
    private static boolean isRing(ListNode node) {
        Map<ListNode, String> map = new HashMap<>();
        while (node != null) {
            if (map.get(node) != null) {
                return true;
            }
            map.put(node, "1");
            node = node.next;
        }
        return false;
    }

    /**
     * 快慢指针法
     *
     * @param node1
     * @param node2
     * @return
     */
    private static ListNode fastAndSlow(ListNode node1, ListNode node2) {
        while (node1 != null && !node1.equals(node2)) {
            System.out.println("node1:" + node1.val + "   node2:" + node2.val);
            node1 = node1.next;
            node2 = node2.next.next;
        }
        return node1;
    }

    // 获取列表长度
    private static int getNodeLength(ListNode node) {
        int length = 0;
        Map<ListNode, String> map = new HashMap<>();
        while (node != null) {
            if (map.get(node) != null) {
                return length;
            }
            map.put(node, "1");
            node = node.next;
            length++;
        }
        return length;
    }

    // map法求解
    private static ListNode map(ListNode node1, ListNode node2) {
        Map<ListNode, String> map = new HashMap<>();
        while (node1 != null) {
            if (map.get(node1) != null) {
                break;
            }
            map.put(node1, "1");
            node1 = node1.next;
        }
        Map<ListNode, String> map1 = new HashMap<>();
        while (node2 != null) {
            if (map.get(node2) != null) {
                return node2;
            }
            if (map1.get(node2) != null) {
                break;
            }
            node2 = node2.next;
        }
        return null;
    }
}
